package sort;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

//46. 全排列
public class Num46_permute {
    private List<List<Integer>> ret = new ArrayList<>();//结果集
    Map<Integer,Boolean> map = new HashMap<>();//判断值是否重复
    public List<List<Integer>> permute(int[] nums) {
        for (int i : nums){
            map.put(i,false);
        }
        //添加结果
        backtracking(nums,new ArrayList<Integer>());
        //返回结果集
        return ret;

    }

    private void backtracking(int[] nums, ArrayList<Integer> list) {
        //递归边界
        if (list.size() == nums.length){
            //添加结果
            ret.add(new ArrayList<>(list));
            return;
        }
        for (int num : nums){
            if (!map.get(num)){
                //没有出现就添加
                list.add(num);
                map.put(num,true);//设置状态
                backtracking(nums,list);
                list.remove(list.size()-1);
                map.put(num,false);
            }
        }
    }
}
